public class HeapSort {
    public static void heapSort(int[] array) {
        createHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            swap(array, 0, end);
            siftDown(array, 0, end);
            end--;
        }
    }

    private static void createHeap(int[] array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent++) {
            siftDown(array, parent, array.length);
        }
    }

    private static void siftDown(int[] array, int parent, int end) {
        int child = parent * 2 - 1;
        while (child < end) {
            if (child + 1 < end && array[child] < array[child + 1]) {
                child++;
            }

            // 此时 child 是两个孩子节点最大的那个
            if (array[child] > array[parent]) {
                swap(array, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else {
                break;
            }
        }
    }
    private static void swap(int[] array, int a, int b) {
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
}
